package com.leetcode.algorithm.y22.m08.w5;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 998. 最大二叉树 II
 * 
 * https://leetcode.cn/problems/maximum-binary-tree-ii/
 * 
 * @author jie.deng
 *
 */
class Question0998Solution01 {

	public TreeNode insertIntoMaxTree(TreeNode root, int val) {
		TreeNode sentinel = new TreeNode(0);
		sentinel.right = root;

		TreeNode prev = sentinel;
		TreeNode cur = root;
		while (cur != null && cur.val > val) {
			prev = cur;
			cur = cur.right;
		}
		prev.right = new TreeNode(val);
		prev.right.left = cur;
		return sentinel.right;
	}

}